public class 零钱兑换 {
    public int coinChange(int[] coins, int amount) {
        // dp 完全背包
        int n = coins.length;
        int INF = 0x3f3f3f3f; // 这个是 min 的判断不需要使用额外判断
        // dp 表
        int[][] dp = new int[n + 1][amount + 1];
        // 前 0 个 amount == j 的多少个硬币
        for (int j = 1;j <= amount;j++) {
            dp[0][j] = INF;
        }
        // 分为选和不选进行判断
        for (int i = 1;i <= n;i++) {
            for (int j = 0;j <= amount;j++) {
                // 不选
                dp[i][j] = dp[i - 1][j];
                // 选
                if (j - coins[i - 1] >= 0) {
                    dp[i][j] = Math.min(dp[i][j],dp[i][j - coins[i - 1]] + 1);
                }
            }
        }
        return dp[n][amount] == INF ? -1 : dp[n][amount];
    }

    // 优化
    public int coinChange1(int[] coins, int amount) {
        // dp
        int n = coins.length;
        int INF = 0x3f3f3f3f;
        int[] dp = new int[amount + 1];
        for (int j = 1;j <= amount;j++) {
            dp[j] = INF;
        }
        for (int i = 1;i <= n;i++) {
            for (int j = coins[i - 1];j <= amount;j++) {
                // 选
                dp[j] = Math.min(dp[j],dp[j - coins[i - 1]] + 1);
            }
        }
        return dp[amount] == INF ? -1 : dp[amount];
    }
}
